The present invention relates to computer programming techniques, and more particularly to techniques for detecting computer memory access errors of a computer program.
Errors arising from improper usage of memory are the most frequently occurring and one of the most intractable class of programming errors. The difficulty in tracking and fixing memory-related errors arises partially because the symptoms of the bug are usually far removed from the actual source of the bug and partially because the symptoms of the bug themselves appear inconsistently. Therefore, debugging of memory management errors requires a systematic, algorithmic approach.
A number of existing tools that aid in the process of debugging of memory-management errors use the technique of inserting run-time tests, either in the source code or in the object code, to validate each memory access during the execution of the program. This straightforward approach implicitly assumes that all memory accesses in the program are independent and unrelated and therefore need to be checked individually, which, unfortunately is not the case in real programs. Also, since most of these techniques tend to validate each memory access in the program, they often slow down the execution of the program by a huge factor; and hence, prove to be very cumbersome to use for industrial-sized programs particularly.
U.S. Pat. No. 5,644,709, issued on 1 Jul. 1997 to Austin describes a method for detecting memory-access errors that occur while executing a computer program (i.e., the errors are only detected at run-time). The method seeks to identify both spatial errors and temporal errors. In the case of a data object, spatial and temporal attributes are associated with a pointer to that data object. On the occurrence of a dereference by a pointer, a memory access check is performed to determine whether the dereference falls outside the valid address range for the data object, or outside a valid time period for the data object. If the dereference falls outside either range, a respective spatial or temporal error is flagged. Thus, U.S. Pat. No. 5,644,709 is concerned with catching memory-access errors only during program code execution (i.e., at run-time).
U.S. Pat. No. 5,644,709 further teaches a necessary preliminary method of taking a source-level program file, which in the normal course of events is compiled, interpreted or translated into object-level code, and adding to that compiling/interpreting/translating process an extended pointer representation. This pointer representation contains the value of the pointer as well as one or more object attributes, which describe the location, size, and lifetime of the pointer reference. This extended form of pointer allows the dereferencing process on occurrence of a memory access to check for spatial and temporal errors.
The approach taught by U.S. Pat. No. 5,644,709 has drawbacks, however, including the fact that errors resulting from source code programming faults are only detected at run-time. While such errors can be detected, the problem of debugging them still exists.
Conventional techniques insert run-time tests in program code (either source code or object code) to perform run-time debugging of memory errors. However, this introduces significant inefficiencies into the debugging process. Thus, a need clearly exists for an improved method of detecting memory-related errors that minimizes detection at run-time of a compiled computer program.
The aspects of the invention perform a static analysis of program source code in an attempt to validate memory accesses in the program at compile-time, for each given program point. Thus the presence or absence of errors can be reported at compile-time. In cases where no conclusion can be reached by the static analysis (e.g. due to the presence of variables whose values cannot be inferred statically), then supplemental run-time tests are provided for validating such memory accesses at run-time.
The aspects of the invention therefore seek to provide a practical and efficient solution to the automatic detection of memory-related errors, using compile-time program analysis to attempt to reduce the extent of run-time testing.
In accordance with a first aspect of the invention, there is disclosed a method of detecting memory-related errors in a computer program during compiling of the computer program. In the method, static analysis is performed upon a computer program. At least one condition in the computer program is computed dependent upon the static analysis. Preferably, a condition is a test for checking a memory access in the computer program to and can be a pre-condition and/or a post-condition. The validity of each condition in the computer program is then evaluated. If the evaluation of a condition is determinate during compiling of the computer program, the presence or absence of memory-related errors in the computer program is reported. Preferably, a condition is determinate if the condition is valid or invalid. Otherwise, if the evaluation of a condition is indeterminate during compiling of the computer program, computer code based on the condition for incorporation in the computer program is generated for run-time detection of memory-related errors in the computer program. In this manner, generated computer code is minimized for run-time detection of memory-related errors in the computer program.
Preferably, the method includes the steps of determining an interrelationship between two or more memory accesses using the static analysis and generating a single condition in the computer program for two or more related memory accesses to minimize the number of conditions to be evaluated. The memory access can be made in the statically allocated memory or the dynamically allocated memory.
Preferably, the method includes the step of assigning at least one precondition to each statement in the computer program that must be satisfied for the computer program to execute without the memory-related errors. The pre-condition depends on one of the following: a memory-related operation in a statement in the computer program; a language restriction imposed on the memory-related operation; a predetermined error capable of being tested for; and a set of pre-conditions for a procedure call, the set being derived from static analysis of source code for the called procedure or being defined by a user. A post-condition is a check on the effect of a statement of the computer program on a memory space and can depend on one of the following: a memory-related operation at the statement of the computer program; the effect of the memory-related operation on the memory space defined by language semantics; and a set of post-conditions for a procedure call, the set being derived from static analysis of source code for the called procedure or being defined by a user.
In accordance with a second aspect of the invention, there is disclosed an apparatus for detecting memory-related errors in a computer program during compiling of the computer program. The apparatus includes a performing device, a computing device, an evaluating device, a reporting device, and a generating device. The performing device performs static analysis upon a computer program. The computing device computes at least one condition in the computer program dependent upon the static analysis. The evaluating device evaluates the validity of the at least one condition in the computer program. The reporting device reports the presence or absence of memory-related errors in the computer program if the evaluation of a condition is determinate during compiling of the computer program. The generating device generates computer code based on the at least one condition for incorporation in the computer program for run-time detection of memory-related errors in the computer program if the evaluation of a condition is indeterminate during compiling of the computer program. In this manner, the generated computer code is minimized for run-time detection of memory-related errors in the computer program.
In accordance with a third aspect of the invention, there is disclosed a computer program product having a computer readable medium having a computer program recorded therein for detecting memory-related errors in a computer program during compiling of the computer program. The computer program product includes:
a computer program code module for performing static analysis upon a computer program;
a computer program code module for computing at least one condition in the computer program dependent upon the static analysis;
a computer program code module for evaluating the validity of the at least one condition in the computer program;
a computer program code module for reporting the presence or absence of memory-related errors in the computer program if the evaluation of a condition is determinate during compiling of the computer program; and
a computer program code module for generating computer code based on the at least one condition for incorporation in the computer program for run-time detection of memory-related errors in the computer program if the evaluation of a condition is indeterminate during compiling of the computer program, whereby the generated computer code is minimized for run-time detection of memory-related errors in the computer program.
In accordance with a fourth aspect of the invention, there is disclosed a method of compiling a computer program. In the method, source code of the computer program is converted into intermediate code of the computer program. The intermediate code, of the computer program is optimized, in which memory-related errors are detected. In the optimization, memory-related errors are detected in the intermediate code of the computer program using static analysis. In the optimization, any memory-related errors in the computer program are reported that are determinate during compiling of the computer program. In the optimization, computer code is generated to test for any memory-related errors in the computer program that are indeterminate during compiling of the computer program. The generated computer code is incorporated in optimized intermediate code of the computer program. The optimized intermediate code is then converted into machine executable code of the computer program.
Preferably, in the detecting step, static analysis is performed upon the intermediate code of the computer program. At least one condition in the intermediate code of the computer program is computed dependent upon the static analysis. The validity of the at least one condition in the intermediate code of the computer program is evaluated.
Each condition checks for a memory access in the computer program. Each condition can be a pre-condition and/or a post-condition. Preferably, the method also includes the steps of determining an interrelationship between two or more memory accesses using the static analysis and generating a single condition in the intermediate code of the computer program for two or more related memory accesses to minimize the number of conditions to be evaluated. A pre-condition can be assigned to each statement in the computer program that must be satisfied for the computer program to execute without the memory-related errors. A post-condition is a check on the effect of a statement of the computer program on a memory space. A condition is determinate if the condition is valid or invalid.
In accordance with a fifth aspect of the invention, there is disclosed an apparatus for compiling a computer program. The apparatus includes a converting device, an optimizing device, and a converting device. The converting device converts source code of the computer program into intermediate code of the computer program. The optimizing device optimizes the intermediate code of the computer program. The converting device converts the optimized intermediate code into machine executable code of the computer program. The optimizing device further includes a detecting device, a reporting device, and a generating device. The detecting device detects memory-related errors in the intermediate code of the computer program using static analysis. The reporting device reports any memory-related errors in the computer program that are determinate during compiling of the computer program. The generating device generates computer code to test for any memory-related errors in the computer program that are indeterminate during compiling of the computer program, the generated computer code incorporated in optimized intermediate code of the computer program.
In accordance with a sixth aspect of the invention, there is disclosed a computer program product having a computer readable medium having a computer program recorded therein for compiling a computer program. The computer program product includes:
a computer program code module for converting source code of the computer program into intermediate code of the computer program;
a computer program code module for optimizing the intermediate code of the computer program, the optimizing module including:
a computer program code module for detecting memory-related errors in the intermediate code of the computer program using static analysis;
a computer program code module for reporting any memory-related errors in the computer program that are determinate during compiling of the computer program; and
a computer program code module for generating computer code to test for any memory-related errors in the computer program that are indeterminate during compiling of the computer program, the generated. computer code incorporated in optimized intermediate code of the computer program; and
a computer program code module for converting the optimized intermediate code into machine executable code of the computer program.